Space-efficient Algorithms for Visibility Problems in Simple Polygon

摘要

Given a simple polygon $P$ consisting of $n$ vertices, we study the problemof designing space-efficient algorithms for computing (i) the visibilitypolygon of a point inside $P$, (ii) the weak visibility polygon of a linesegment inside $P$ and (iii) the minimum link path between a pair of pointsinside $P$. For problem (i) two algorithms are proposed. The first one is anin-place algorithm where the input array may be lost. It uses only O(1) extraspace apart from the input array. The second one assumes that the input isgiven in a read-only array, and it needs $O(\sqrt{n})$ extra space. The timecomplexity of both the algorithms are O(n). For problem (ii), we have assumedthat the input polygon is given in a read-only array. Our proposed algorithmruns in $O(n^2)$ time using O(1) extra space. For problem (iii) the time andspace complexities of our proposed algorithm are $O(kn)$ and O(1) respectively;$k$ is the length (number of links) in a minimum link path between the givenpair of points.